package com.wangping.algorithm.sort;

import java.util.Arrays;

/**
 * @author wangping
 * @version V1.0
 * @date 2018/12/5 16:59
 */
public class MergeSort {

    public void sort(int[] ints) {
        mergeSort(ints, 0, ints.length);
    }

    /**
     * 对数组[lo..hi)进行排序
     *
     * @param ints 待排序数组
     * @param lo   left
     * @param hi   right
     */
    private void mergeSort(int[] ints, int lo, int hi) {
        if (ints.length == 1) {
            return;
        }
        int mid = ints.length / 2;
        int[] left = new int[mid];
        System.arraycopy(ints, 0, left, 0, left.length);

        int[] right = new int[ints.length - mid];
        System.arraycopy(ints, mid, right, 0, right.length);

        mergeSort(left, 0, left.length);
        mergeSort(right, 0, right.length);
        merge(left, right, ints);
    }

    /**
     * 合并操作 a+b->dst 数组a,数组b合并到数组dst
     *
     * @param a
     * @param b
     * @param dst
     */
    private void merge(int[] a, int[] b, int[] dst) {
        if (dst.length != a.length + b.length) {
            throw new RuntimeException("异常,合并数量不相等");
        }
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            if (a[i] - b[j] < 0) {
                dst[k] = a[i];
                k++;
                i++;
            } else {
                dst[k] = b[j];
                k++;
                j++;
            }

        }

        if (i == a.length) {
            System.arraycopy(b, j, dst, k, dst.length - k);
        } else {
            System.arraycopy(a, i, dst, k, dst.length - k);
        }
    }

    public static void main(String[] args) {
        int[] ints = {1, 4, 2, 99, 55, 3, 33, 2, 2, 1, 88, 22, 222, 333, 11};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(ints);
        System.out.println(Arrays.toString(ints));
    }
}
